//定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。 
//
// 
//
// 示例: 
//
// 输入: 1->2->3->4->5->NULL
//输出: 5->4->3->2->1->NULL 
//
// 
//
// 限制： 
//
// 0 <= 节点个数 <= 5000 
//
// 
//
// 注意：本题与主站 206 题相同：https://leetcode-cn.com/problems/reverse-linked-list/ 
// Related Topics 递归 链表 👍 435 👎 0

package leetcode.editor.offer;

class FanZhuanLianBiaoLcof {
    public static void main(String[] args) {
        Solution solution = new FanZhuanLianBiaoLcof().new Solution();
    }
    //leetcode submit region begin(Prohibit modification and deletion)


    //      Definition for singly-linked list.
    public class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
        }
    }

    class Solution {
//        public ListNode reverseList(ListNode head) {
//            if (head == null) {
//                return null;
//            }
//            if (head.next == null) {
//                return null;
//            }
//            ListNode pre = head.next;
//            ListNode cur = pre.next;
//            head.next = null;
//            while (cur != null) {
//                pre.next = head;
//                head = pre;
//                pre = cur;
//                cur = cur.next;
//            }
//            // 最后一步
//            pre.next = head;
//            return pre;
//        }

        /**
         * 简化方法（暂存后继节点）
         *
         * @param head
         * @return
         */
//        public ListNode reverseList(ListNode head) {
//            ListNode cur = head, pre = null;
//            while (cur != null) {
//                ListNode temp = cur.next;   // 暂时保存后面一个节点
//                cur.next = pre; // 交换指向
//                pre = cur;
//                cur = temp;
//            }
//            return head;
//        }
        public ListNode reverseList(ListNode head) {
            // return recur(null, head);
            return recur(head);
        }

        public ListNode recur(ListNode pre, ListNode cur) {
            if (cur == null) return pre;    // 递归的中止条件
            ListNode temp = cur.next;
            cur.next = pre;
            return recur(cur, temp);
        }

        public ListNode recur(ListNode head) {
            if (head == null || head.next == null) return head;
            ListNode last = recur(head.next);
            head.next.next = head;
            head.next = null;
            return last;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}
